// 创建双向链表的构造函数
function DoublyLinkedList() {
  // 创建节点构造函数
  function Node(element) {
    this.element = element;
    this.next = null;
    this.prev = null; // 新添加的
  }

  // 定义属性
  this.length = 0;
  this.head = null;
  this.tail = null; // 新添加的

  // 定义相关操作方法
  // 在尾部追加数据
  this.append = function (element) {
    // 1.根据元素创建节点
    let newNode = new Node(element);

    // 2.判断列表是否为空列表
    if (this.head == null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }

    // 3.length+1
    this.length++;
  };

  // 在任意位置插入数据
  this.insert = function (position, element) {
    // 1.判断越界的问题
    if (position < 0 || position > this.length) return false;

    // 2.创建新的节点
    let newNode = new Node(element);

    // 3.判断插入的位置
    if (position === 0) {
      // 在第一个位置插入数据
      // 判断链表是否为空
      if (this.head == null) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        this.head.prev = newNode;
        newNode.next = this.head;
        this.head = newNode;
      }
    } else if (position === this.length) {
      // 插入到最后的情况
      // 思考: 这种情况是否需要判断链表为空的情况呢? 答案是不需要, 为什么?
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    } else {
      // 在中间位置插入数据
      // 定义属性
      let index = 0;
      let current = this.head;
      let previous = null;

      // 查找正确的位置
      while (index++ < position) {
        previous = current;
        current = current.next;
      }

      // 交换节点的指向顺序
      newNode.next = current;
      newNode.prev = previous;
      current.prev = newNode;
      previous.next = newNode;
    }

    // 4.length+1
    this.length++;

    return true;
  };

  // 根据位置删除对应的元素
  this.removeAt = function (position) {
    // 1.判断越界的问题
    if (position < 0 || position >= this.length) return null;

    // 2.判断移除的位置
    let current = this.head;
    if (position === 0) {
      if (this.length == 1) {
        this.head = null;
        this.tail = null;
      } else {
        this.head = this.head.next;
        this.head.prev = null;
      }
    } else if (position === this.length - 1) {
      current = this.tail;
      this.tail = this.tail.prev;
      this.tail.next = null;
    } else {
      let index = 0;
      let previous = null;

      while (index++ < position) {
        previous = current;
        current = current.next;
      }

      previous.next = current.next;
      current.next.prev = previous;
    }

    // 3.length-1
    this.length--;

    return current.element;
  };

  // 根据元素获取在链表中的位置
  this.indexOf = function (element) {
    // 1.定义变量保存信息
    let current = this.head;
    let index = 0;

    // 2.查找正确的信息
    while (current) {
      if (current.element === element) {
        return index;
      }
      index++;
      current = current.next;
    }

    // 3.来到这个位置, 说明没有找到, 则返回-1
    return -1;
  };

  // 根据元素删除
  this.remove = function (element) {
    let index = this.indexOf(element);
    return this.removeAt(index);
  };

  // 判断是否为空
  this.isEmpty = function () {
    return this.length === 0;
  };

  // 获取链表长度
  this.size = function () {
    return this.length;
  };

  // 获取第一个元素
  this.getHead = function () {
    return this.head.element;
  };

  // 获取最后一个元素
  this.getTail = function () {
    return this.tail.element;
  };

  // 遍历方法的实现
  // 正向遍历的方法
  this.forwardString = function () {
    let current = this.head;
    let forwardStr = "";

    while (current) {
      forwardStr += "," + current.element;
      current = current.next;
    }

    return forwardStr.slice(1);
  };

  // 反向遍历的方法
  this.reverseString = function () {
    let current = this.tail;
    let reverseStr = "";

    while (current) {
      reverseStr += "," + current.element;
      current = current.prev;
    }

    return reverseStr.slice(1);
  };

  // 实现toString方法
  this.toString = function () {
    return this.forwardString();
  };
}

// let demo = new DoublyLinkedList();
// demo.append(1);
// demo.append(2);
// demo.append(3);

// console.log("实例的长度 -", demo.length);
// // 正向遍历的方法
// console.log("正向遍历的方法 -", demo.forwardString());
// // 反向遍历的方法
// console.log("正向遍历的方法 -", demo.reverseString());

//  --------------------------------------------------
//  --------------------------------------------------
//  --------------------Class写法---------------------
//  --------------------------------------------------
//  --------------------------------------------------

// 节点类 包括值和前后节点的指向
class Node {
  constructor(value) {
    this.val = value;
    // 下一个节点
    this.next = null;
    // 上一个节点
    this.pre = null;
  }
}

class DoubleLinkedList {
  constructor() {
    // 构建的基础属性 长度 头节点 尾节点
    this.length = 0;
    this.head = null;
    this.tail = null;
  }
  // 在尾部追加数据
  append(value) {
    // 1.根据元素创建节点
    let newNode = new Node(value);
    // 2.判断链表是否为空链表
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 要先把尾节点的next指到新节点
      this.tail.next = newNode;
      newNode.pre = this.tail;
      // 再将新节点设置为尾节点
      this.tail = newNode;
    }
    this.length++;
  }
  // 在任意位置插入数据
  insert(position, value) {
    // 1.创建新的节点
    let newNode = new Node(value);
    // 2.判断越界的问题
    if (position < 0 || position > this.length) {
      return false;
    }
    // 3.判断插入的位置
    if (position === 0) {
      // 在第一个位置插入数据
      // 判断链表是否为空
      if (!this.head) {
        // 链表为空时
        this.head = newNode;
        this.tail = newNode;
      } else {
        // 当链表不是空的时候
        // 要先把原来的头节点的pre指向新节点
        this.head.pre = newNode;
        newNode.next = this.head;
        // 再把新节点设置为头节点
        this.head = newNode;
      }
    } else if (position === this.length) {
      // 插入到最后的情况
      // 思考: 这种情况是否需要判断链表为空的情况呢? 答案是不需要, 为什么?
      this.tail.next = newNode;
      newNode.pre = this.tail;
      this.tail = newNode;
    } else {
      // 在中间位置插入数据
      // 定义属性
      let index = 0;
      let current = this.head;
      let previous = null;
      // 查找要插入的位置
      while (index < position) {
        previous = current;
        current = current.next;
        // pre保存的是current前一个节点
        index++;
      }
      // 交换节点的指向顺序
      newNode.next = current;
      newNode.pre = previous;
      current.pre = newNode;
      previous.next = newNode;
    }
    // 4.length+1
    this.length++;
  }
  // 根据位置删除对应的元素
  removeAt(position) {
    // 1.判断越界的问题
    if (position < 0 || position > this.length) {
      return false;
    }
    // 2.判断移除的位置
    let current = this.head;
    if (position === 0) {
      if (this.length === 1) {
        this.head = null;
        this.tail = null;
      } else {
        this.head = this.head.next;
        this.head.pre = null;
      }
    } else if (position === this.length - 1) {
      current = this.tail;
      this.tail = this.tail.pre;
      this.tail.next = null;
    } else {
      let index = 0;
      let previous = null;
      while (index < position) {
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
      current.next.prev = previous;
    }
    // 3.length-1
    this.length++;
    return current.val;
  }
  // 根据元素删除
  remove(val) {
    let index = this.indexOf(val);
    return this.removeAt(index);
  }
  // 根据元素获取在链表中的位置
  indexOf(value) {
    // 1.定义变量保存信息
    let current = this.head;
    let index = 0;

    // 2.查找正确的信息
    while (current) {
      if (current.val === value) {
        return index;
      }
      index++;
      current = current.next;
    }

    // 3.来到这个位置, 说明没有找到, 则返回-1
    return -1;
  }
  // 判断是否为空
  isEmpty() {
    return this.length === 0;
  }
  // 获取链表长度
  size() {
    return this.length;
  }
  // 获取第一个元素
  getHead() {
    return this.head.val;
  }
  // 获取最后一个元素
  getTail() {
    return this.tail.val;
  }
  // 遍历方法的实现
  // 正向遍历的方法
  forwardString() {
    let current = this.head;
    let forwardStr = "";

    while (current) {
      forwardStr += "," + current.val;
      current = current.next;
    }

    return forwardStr.slice(1);
  }
  // 反向遍历的方法
  reverseString() {
    let current = this.tail;
    let reverseStr = "";

    while (current) {
      reverseStr += "," + current.val;
      current = current.pre;
    }

    return reverseStr.slice(1);
  }
  // 实现toString方法
  toString() {
    return this.forwardString();
  }
}

let ins = new DoubleLinkedList();
ins.append(1);
ins.append(2);
ins.append(3);
ins.append(4);
console.log(ins.forwardString());
console.log("---------------------------");
ins.insert(2, 9999);
console.log(ins.forwardString());
console.log("---------------------------");
ins.removeAt(0);
console.log(ins.forwardString());
console.log("---------------------------");
console.log(ins.indexOf(9999));
console.log("---------------------------");
console.log(ins.reverseString());
console.log("---------------------------");
console.log(ins.getHead());
console.log("---------------------------");
console.log(ins.getTail());
console.log("---------------------------");
console.log(ins.isEmpty());

console.log("---------------------------");
console.log(ins.size());
